home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / C / ESPRESSO.ZIP / SET.H < prev    next >
Encoding:
C/C++ Source or Header  |  1987-03-14  |  6.3 KB  |  143 lines
  1. /*
  2.     set.h -- definitions for packed arrays of bits
  3.  
  4.     This header file describes the data structures which comprise a
  5.     facility for efficiently implementing packed arrays of bits
  6.     (otherwise known as sets, cf. Pascal).
  7.  
  8.     A set is a vector of bits and is implemented here as an array of
  9.     unsigned integers.  The low order bits of set[0] give the index
  10.     of the last word of set data.  The higher order bits of set[0] are
  11.     used to store data associated with the set.  The set data is
  12.     contained in elements set[1] ... set[LOOP(set)] as a packed bit
  13.     array.
  14.  
  15.     A family of sets is a two-dimensional matrix of bits and is
  16.     implemented with the data type "set_family".
  17. */
  18.  
  19. /* Define host machine characteristics of "unsigned int" */
  20. #define BPI             16              /* # bits per integer */
  21. #define LOGBPI          4               /* log(BPI)/log(2) */
  22.  
  23. /* Define the set type */
  24. typedef unsigned *pset;
  25.  
  26. /* Define the set family type -- an array of sets */
  27. typedef struct set_family {
  28.     int wsize;                  /* Size of each set in 'ints' */
  29.     int sf_size;                /* User declared set size */
  30.     int capacity;               /* Number of sets allocated */
  31.     int count;                  /* The number of sets in the family */
  32.     int active_count;           /* Number of "active" sets */
  33.     pset data;                  /* Pointer to the set data */
  34.     struct set_family *next;    /* For garbage collection */
  35. } set_family_t, *pset_family;
  36.  
  37. /* Macros to set and test single elements */
  38. #define WHICH_WORD(element)     (((element) >> LOGBPI) + 1)
  39. #define WHICH_BIT(element)      (1 << ((element) & (BPI-1)))
  40.  
  41. /* # of ints needed to allocate a set with "size" elements */
  42. #if BPI == 32
  43. #define SET_SIZE(size)          ((size) <= 0 ? 2 : (WHICH_WORD((size)-1) + 1))
  44. #else
  45. #define SET_SIZE(size)          ((size) <= 0 ? 3 : (WHICH_WORD((size)-1) + 2))
  46. #endif
  47.  
  48. /*
  49.   Three fields are maintained in the first word of the set
  50.         LOOP is the index of the last word used for set data
  51.         LOOPCOPY is the index of the last word in the set
  52.         SIZE is available for general use (e.g., storing set size)
  53.         FLAGS store general information about the set
  54. */
  55. #define LOOP(set)               (set[0] & 0x03ff)
  56. #define PUTLOOP(set, i)         (set[0] &= ~0x03ff, set[0] |= (i))
  57. #if BPI == 32
  58. #define LOOPCOPY(set)           LOOP(set)
  59. #define SIZE(set)               (set[0] >> 16)
  60. #define PUTSIZE(set, size)      (set[0] &= 0xffff, set[0] |= ((size) << 16))
  61. #else
  62. #define LOOPCOPY(set)           (LOOP(set) + 1)
  63. #define SIZE(set)               (set[LOOP(set)+1])
  64. #define PUTSIZE(set, size)      ((set[LOOP(set)+1]) = (size))
  65. #endif
  66. #define SET(set, flag)          (set[0] |= (flag))
  67. #define RESET(set, flag)        (set[0] &= ~ (flag))
  68. #define TESTP(set, flag)        (set[0] & (flag))
  69.  
  70. /* Flag definitions are ... */
  71. #define PRIME           0x8000          /* cube is prime */
  72. #define NONESSEN        0x4000          /* cube cannot be essential prime */
  73. #define ACTIVE          0x2000          /* cube is still active */
  74. #define REDUND          0x1000          /* cube is redundant(at this point) */
  75. #define COVERED         0x0800          /* cube has been covered */
  76. #define RELESSEN        0x0400          /* cube is relatively essential */
  77.  
  78. /* Most efficient way to look at all members of a set family */
  79. #define foreach_set(R, last, p) \
  80.     for(p=R->data,last=p+R->count*R->wsize;p<last;p+=R->wsize)
  81. #define foreach_remaining_set(R, last, pfirst, p) \
  82.     for(p=pfirst+R->wsize,last=R->data+R->count*R->wsize;p<last;p+=R->wsize)
  83. #define foreach_active_set(R, last, p) \
  84.     foreach_set(R,last,p) if (TESTP(p, ACTIVE))
  85.  
  86. /* Another way that also keeps the index of the current set member in i */
  87. #define foreachi_set(R, i, p) \
  88.     for(p=R->data,i=0;i<R->count;p+=R->wsize,i++)
  89. #define foreachi_active_set(R, i, p) \
  90.     foreachi_set(R,i,p) if (TESTP(p, ACTIVE))
  91.  
  92. /* Return a pointer to a given member of a set family */
  93. #define GETSET(family, index)   ((family)->data + (family)->wsize * (index))
  94.  
  95. /* Allocate and deallocate sets */
  96. #define set_new(size) /*NOSTRICT*/ \
  97.     set_clear((pset) alloc(SET_SIZE(size)*sizeof(int)),size)
  98. #define set_save(r)   /*NOSTRICT*/ \
  99.     set_copy((pset) alloc((int) (SET_SIZE(LOOP(r)*BPI))*sizeof(int)), r)
  100. #define set_free(r)   /*NOSTRICT*/ \
  101.     mem_free((char *) r)
  102.  
  103. /* Check for set membership, remove set element and insert set element */
  104. #define is_in_set(set, e)       (set[WHICH_WORD(e)] & WHICH_BIT(e))
  105. #define set_remove(set, e)      (set[WHICH_WORD(e)] &= ~ WHICH_BIT(e))
  106. #define set_insert(set, e)      (set[WHICH_WORD(e)] |= WHICH_BIT(e))
  107.  
  108. /* Inline code substitution for those places that REALLY need it on a VAX */
  109. #define INLINEset_copy(r, a) \
  110. {register i_=LOOPCOPY(a); do r[i_] = a[i_]; while (--i_ >= 0);}
  111. #define INLINEset_clear(r, size) \
  112. {register i_=WHICH_WORD(size-1); *r=i_; do r[i_] = 0; while (--i_ > 0);}
  113. #define INLINEset_and(r, a, b) \
  114. {register i_=LOOP(a); PUTLOOP(r,i_); do r[i_] = a[i_]&b[i_]; while (--i_>0);}
  115. #define INLINEset_or(r, a, b) \
  116. {register i_=LOOP(a); PUTLOOP(r,i_); do r[i_] = a[i_]|b[i_]; while (--i_>0);}
  117. #define INLINEset_diff(r, a, b) \
  118. {register i_=LOOP(a); PUTLOOP(r,i_); do r[i_] = a[i_]&~b[i_]; while (--i_>0);}
  119. #define INLINEsetp_implies(a, b, when_false) \
  120. {register i_=LOOP(a); do if (a[i_]&~b[i_]) break; while (--i_>0); \
  121. if (i_ != 0) when_false;}
  122.  
  123. #if BPI == 32
  124. #define count_ones(v)   (bit_count[v & 255] + bit_count[(v >> 8) & 255] \
  125.     + bit_count[(v >> 16) & 255] + bit_count[(v >> 24) & 255])
  126. #else
  127. #define count_ones(v)   (bit_count[v & 255] + bit_count[(v >> 8) & 255])
  128. #endif
  129.  
  130. /* Table for efficient bit counting */
  131. EXTERN int bit_count[256]
  132. #ifdef INIT
  133. ={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
  134.   1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  135.   1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  136.   2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
  137.   1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  138.   2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
  139.   2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
  140.   3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8}
  141. #endif
  142. ;
  143.